package algorithm.sort;

import algorithm.RandomArr;
import org.junit.Test;

import java.util.Arrays;

public class KuaiSuSort1 {

  @Test
  public void test() {

    this.arr = RandomArr.Arr(4);
    System.out.println(Arrays.toString(this.arr));
    int i = kuaiSu(0, this.arr.length - 1);
    System.out.println(i);
    System.out.println(Arrays.toString(this.arr));


  }


  @Test
  public void test3() {
    for (int i = 0; i < 10; i++) {

      this.arr = RandomArr.Arr(100);
      sort(0, this.arr.length - 1);
      System.out.println(Arrays.toString(this.arr));

      int pre = this.arr[0];
      for (int j = 0; j < this.arr.length; j++) {
        if (pre > this.arr[j]) {
          System.out.println("验证未通过");
          System.out.println(Arrays.toString(this.arr));
          break;
        } else {
          pre = this.arr[j];
        }
      }
    }

  }

  int[] arr = null;

  public void sort(int low, int high) {
    if (low >= high) return;
    int mid = kuaiSu(low, high);

    sort(low, mid - 1);
    sort(mid + 1, high);

  }

  // [low,high]
  public int kuaiSu(int low, int high) {

    if (low >= high) return low;

    //基数
    int k = this.arr[low];

    //跳过k 基数
    int i = low + 1;
    int j = high;

    while (true) {
      // i 往 右移动，直到到头 或者 大于基数的值
      while (i < high && this.arr[i] <= k) {
        i++;
      }
      //
      while (j > low && this.arr[j] > k) {
        j--;
      }
      if (i < j) {
        //互换
        int tmp = this.arr[j];
        this.arr[j] = this.arr[i];
        this.arr[i] = tmp;
      } else {
        break;
      }
    }

    //
    int tmp = this.arr[low];
    this.arr[low] = this.arr[j];
    this.arr[j] = tmp;

    return j;
  }


}
